package com.test.suanfa;

import java.util.*;

/**
 * 优势洗牌：
 * 给定两个大小相同的数组A和B，返回A的任意排列，使其相对于B的优势最大
 */
public class 优势洗牌 {

    private static int[] A = {11, 9, 14, 17, 13, 19};
    // 基准数组
    private static int[] B = {20, 16, 21, 12, 10, 16};

    public static void main(String[] args) {
        t1();
    }

    private static void t1(){
        int[] tmpB = B.clone();
        Arrays.sort(A);
        Arrays.sort(tmpB);

        Deque<Integer> laji = new LinkedList<>();
        // 准备一个连表做FIFO
        Map<Integer, Deque<Integer>> map = new HashMap<>();
        for (int b : tmpB) {
            map.put(b, new LinkedList<>());
        }

        int j = 0;
        for (int a : A) {
            if (a > tmpB[j]) {
                map.get(tmpB[j]).add(a);
                j++;
            } else {
                laji.add(a);
            }
        }

        int[] ans = new int[B.length];
        for (int i = 0; i < B.length; i++) {
            if (map.get(B[i]).size()>0){
                ans[i] = map.get(B[i]).removeLast();
            }else{
                ans[i] = laji.removeLast();
            }
        }
    }
}